1. Field of the Invention
This invention relates generally to non-volatile memory, and more particularly to providing memory management in a non-volatile memory system using a block table stored in non-volatile memory.
2. Description of the Related Art
In general, non-volatile memory is memory that stores data when power is disconnected from the system. Phase-change memory (PCM) and flash memory are examples of non-volatile computer memory in use today. Flash memory is a non-volatile computer memory that can be electrically erased and reprogrammed. Because flash memory retains stored data even when power to the memory is turned off, flash memory is widely used in battery-driven portable devices. For example, flash memory often is utilized in digital audio players, digital cameras, mobile phones, and USB flash drives, which are used for general storage and transfer of data between computers.
FIG. 1 is an illustration showing a typical prior art non-volatile memory arrangement. As illustrated in FIG. 1, a non-volatile memory 100 generally comprises a plurality of memory blocks 102, which generally is the smallest portion of memory that can be erased, as will be described in greater detail below. Each memory block 102 generally comprises a fixed plurality of pages 104, which is the smallest size element that can be written or read from the non-volatile memory 100. Each page 104 generally is logically divided into two areas: a main area 106 and a spare area 108. For example, a typical non-volatile memory will have a main area 106 of 2048 bytes and a spare area 108 of 64 bytes.
Prior art non-volatile memory systems generally utilize the main area 106 to store user data and the spare area 108 to store non-volatile memory system data, which is not generally utilized by the user. The non-volatile memory system data typically includes error correction code (ECC), flags, pointers, and other data that is useful for the non-volatile memory system to operate, as illustrated by Table 1.
blockStateBlock state. non = 0xFF1bytefor bad blockchunkID32-bit chunk ID4bytesobjectID32-bit object ID4bytesnBytesNumber of data bytes in2bytesthis chunkblockSequencesequence number for this4bytesblocktagsEccECC on tags area3byteseccECC, 3 bytes/256 bytes24bytesof dataTotal42bytes
Table 1 illustrates exemplary prior art spare area 108 usage for the YAFFS2 flash file system, which is a public domain flash file system well known in the art. As shown in Table 1, typical flash file systems use the spare area to store, inter alia, the block state, logical and physical address mapping for the page or block, and error correction code logic. The bytes allowed for ECC in the prior art spare area 108 work adequately for Single Level Cell (SLC) memory, which contains one bit of data in each memory cell. However, as demand for greater functionality in devices has increased, so has demand for flash memory with greater storage capacity. To address such demands, multilevel-cell (MLC) memory has been developed. MLC memory cells contain two or more bits of data, thereby increasing the storage capacity of the device.
MLC memory is much less reliable than SLC memory. Because MLC devices have a higher intrinsic bit error rate, MLC devices require more powerful ECC. To support the required level of data integrity, MLC memory typically requires thirteen ECC check bytes for every 512 bytes of user data. Thus, for pages having a main area 106 of 2048 bytes, fifty-two check bytes are required. As can be appreciated from Table 1, utilizing fifty-two check bytes in the spare area 108 begins to cause space conflicts with other non-volatile memory system data stored in the spare area 108 utilizing prior art non-volatile memory management techniques.
In addition, unlike many other storage devices, non-volatile memory devices generally cannot be overwritten. Instead, to update data in a particular storage location within non-volatile memory, the location must first be erased, then the new data written in its place. Moreover, when erasing data in a flash device, an entire block must be erased instead of just the particular page or pages of the block that were updated. To facilitate this process, a typical flash controller will find a block of memory that has been previously erased and write the updated page to this new block at the same page offset. Then, the remaining pages of the old block are copied to the new block. Later, the old block is erased and made available for use by some other operation.
As can be appreciated writing data to memory in this manner can lead to problems unless a careful mapping of logical addresses to physical addresses is maintained. In prior art systems, this mapping generally is accomplished utilizing the spare area 108 of each page. Typically, in a page level mapping, the spare area 108 of each physical page 104 stores a logical address of the data that is physically written in the main area 106 of that page 104. To maintain this data in a usable format, prior art systems typically generate a page table at power-up, as illustrated next with reference to FIGS. 2A and 2B.
FIG. 2A is a table showing a prior art unsorted and unorganized page table 200 generated during power-up. The prior art page table 200 comprises a plurality of physical page address entries 202 and a plurality of logical page address entries 204 and is generated each time the system powers-up. During power-up, prior art non-volatile memory systems using page level mapping typically examine the spare area 108 of each page 104 to obtain the logical address of the data that is physically written in the main area 106 of the particular page 104. This data is then entered into the page table 200 and the next page is examined. For example, the non-volatile memory system examines physical page 0 of block 0. In the example of FIG. 2A, the logical page address 4 is stored in the spare area 106 of page 0. Hence, the physical page 0 is associated with logical page 4 in the page table 200. The system then examines the spare area 108 of physical page 1 and finds, in the example of FIG. 2A, logical page address 61 stored in the spare area 108. Hence, the physical page 1 is associated with logical page 61 in the page table 200. This continues until all the spare area of all pages 104 in the non-volatile memory 100 have been examined and mapped to the page table 200. Once the address data is read into the page table 200, the page table 200 is sorted to make the data more usable to the system.
FIG. 2B is a table showing a prior art sorted and organized page table 200′ sorted during power-up. In general, when sorting the page table 200′, the system arranges the page table 200′ in logical address 204 order. In this manner, when access to data associated with a particular logical address 204 is needed, the page table 200′ can be consulted at the entry associated with the particular logical address 204 and the actual physical address 202 within non-volatile memory of the data can be determined. As can be appreciated, when there are a large number of pages in the non-volatile memory, the page table 200 can be large. As such, it can take a long time to generate, organize, and sort the data of the page table 200 each time the system powers-up.
In view of the foregoing, there is a need for systems and methods for providing memory management in a non-volatile memory. The systems and methods should allow for effective use of the spare area to allow adequate space for increased error correction code usage. In addition, the systems and methods should reduce the amount of time required during power-up to produce a usable table in system memory.